//给定两个数组，编写一个函数来计算它们的交集。 
//
// 示例 1: 
//
// 输入: nums1 = [1,2,2,1], nums2 = [2,2]
//输出: [2,2]
// 
//
// 示例 2: 
//
// 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出: [4,9] 
//
// 说明： 
//
// 
// 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。 
// 我们可以不考虑输出结果的顺序。 
// 
//
// 进阶: 
//
// 
// 如果给定的数组已经排好序呢？你将如何优化你的算法？ 
// 如果 nums1 的大小比 nums2 小很多，哪种方法更优？ 
// 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 
// 
// Related Topics 排序 哈希表 双指针 二分查找

package leetcode.editor.cn;
public class IntersectionOfTwoArraysIi {
    public static void main(String[] args) {
        Solution solution = new IntersectionOfTwoArraysIi().new Solution();
        printArray(solution.intersect(new int[]{3,1,2},
                new int[]{1,1}));

    }

    public static void printArray(int array[]) {
        if (array != null) {
            for (int i : array) {
                System.out.println(i);
            }
            System.out.println("---------------------- end");
        }
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int empty[] = new int[0];
        if (nums1 == null || nums2 == null) {
            return empty;
        }

//            quitckSort(nums1, 0, nums1.length - 1);
//            quitckSort(nums2, 0, nums2.length - 1);

        if (nums1.length <= nums2.length) {
            int[] sameIndexArray = new int[nums1.length];
            int i = 0;
            int ii = 0;

            int[] excludeIndexArray = new int[nums2.length];
            int e = 0;
            int excludeActualLength = 0;
            for (; i < nums1.length; i++) {
                for (int jj = 0; jj < nums2.length; jj++) {
                    if (nums1[i] == nums2[jj]) {
                        boolean found = false;
                        for (int kk = 0; kk < excludeActualLength; kk++) {
                            if (excludeIndexArray[kk] == jj) {
                                found = true;
                                break;
                            }
                        }
                        if (found) {
                            continue;
                        }

                        excludeIndexArray[e] = jj;
                        e++;
                        excludeActualLength ++;
                        sameIndexArray[ii] = i;
                        ii++;
                        break;
                    }
                }
            }

            if (ii == 0) {
                return empty;
            }


            int result[] = new int[ii];
            int sameIndexArrayLength = ii;
            ii = 0;
            for (int j = 0; j < sameIndexArrayLength && ii < sameIndexArrayLength;
                 j++) {
                int num = nums1[sameIndexArray[ii]];
                result[j] = num;
                ii++;
            }

            if (result.length == 0) {
                return empty;
            }


            return result;
        } else {
            int[] excludeIndexArray = new int[nums2.length];
            int e = 0;
            int excludeActualLength = 0;
            int[] sameIndexArray = new int[nums2.length];
            int i = 0;
            int ii = 0;
            for (; i < nums2.length; i++) {
                for (int jj = 0; jj < nums1.length; jj++) {
                    if (nums2[i] == nums1[jj]) {
                        boolean found = false;
                        for (int kk = 0; kk < excludeActualLength; kk++) {
                            if (excludeIndexArray[kk] == jj) {
                                found = true;
                                break;
                            }
                        }
                        if (found) {
                            continue;
                        }

                        excludeIndexArray[e] = jj;
                        e++;
                        excludeActualLength ++;

                        sameIndexArray[ii] = i;
                        ii++;
                        break;
                    }
                }
            }

            if (ii == 0) {
                return empty;
            }


            int result[] = new int[ii];
            int sameIndexArrayLength = ii;
            ii = 0;
            for (int j = 0; j < sameIndexArrayLength && ii < sameIndexArrayLength;
                 j++) {
                int num = nums2[sameIndexArray[ii]];
                result[j] = num;
                ii++;
            }


            if (result.length == 0) {
                return empty;
            }


            return result;
        }

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}